#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

class BSTIterator {
  public:
    BSTIterator(BinaryTreeNode* root) :
      cur_node_(root) {};

    bool hasNext() {
      return (cur_node_ || !stack_help.empty());
    }

    BinaryTreeNode* next() {
      while (cur_node_) {
        stack_help.push(cur_node_);
        cur_node_ = cur_node_->left;
      }
      cur_node_ = stack_help.top();
      stack_help.pop();
      next_node_ = cur_node_;
      cur_node_ = cur_node_->right;
      return next_node_;
    }

  private:
    BinaryTreeNode* cur_node_;
    BinaryTreeNode* next_node_;
    stack<BinaryTreeNode*> stack_help;
};

int main() {
  vector<int> vec = {2, 1, 3};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  BSTIterator iter(root);
  cout << iter.hasNext() << endl;
  cout << iter.next()->value << endl;
  cout << iter.hasNext() << endl;
  cout << iter.next()->value << endl;
  cout << iter.hasNext() << endl;
  cout << iter.next()->value << endl;
  cout << iter.hasNext() << endl;

  return 0;
}
